/**
 * //在一个数组 nums 中除一个数字只出现一次之外，其他数字都出现了三次。请找出那个只出现一次的数字。
 * //
 * //
 * //
 * // 示例 1：
 * //
 * // 输入：nums = [3,4,3,3]
 * //输出：4
 * //
 * //
 * // 示例 2：
 * //
 * // 输入：nums = [9,1,7,9,7,9,7]
 * //输出：1
 * //
 * //
 * //
 * // 限制：
 * //
 * //
 * // 1 <= nums.length <= 10000
 * // 1 <= nums[i] < 2^31
 * //
 * //
 * //
 * //
 * // Related Topics 位运算 数组 👍 389 👎 0
 */

package com.xixi.basicAlgroithms.bitManipulation;

import java.util.HashMap;
import java.util.Map;

public class ID_Offer_56_II_ShuZuZhongShuZiChuXianDeCiShuIiLcof {
    public static void main(String[] args) {
        Solution solution = new ID_Offer_56_II_ShuZuZhongShuZiChuXianDeCiShuIiLcof().new Solution();
    }

    //bit运算
    public int singleNumber(int[] nums) {

        int[] bitSum = new int[32];

        for (int num : nums) {
            int nowNum = num;
            int index = 0;
            while (index < 32) {
                //记录二进制位为1的
                if ((nowNum & 1) == 1) {
                    if (bitSum[index] == 2) {
                        bitSum[index] = 0;//逢3变0
                    } else {
                        bitSum[index]++;
                    }
                }
                nowNum >>>= 1;
                index++;
            }
        }

        int res = 0;
        for (int i = 0; i < bitSum.length; i++) {
            if (bitSum[i] == 1) {
                res += bitSum[i] << i;
            }
        }
        return res;

    }


    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int singleNumber(int[] nums) {

            Map<Integer, Integer> numTimes = new HashMap<>();

            for (int i = 0; i < nums.length; i++) {
                Integer times = numTimes.putIfAbsent(nums[i], 1);
                if (times != null) {
                    numTimes.put(nums[i], times + 1);
                }

            }

            for (Map.Entry<Integer, Integer> entry : numTimes.entrySet()) {

                if (entry.getValue() < 3) {
                    return entry.getKey();
                }

            }

            return 0;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)


}